#-*- encoding=utf-8 -*-
'''
Created on 2013. 9. 9.

@author: jylee
'''

class Tree:
	'''
	Abstract class of tree structure.
	'''


	class Position:
		"location of single element."

		def element(self):
			raise NotImplementedError();

		def __eq__ (self, other):
			raise NotImplementedError();

		def __ne__(self, other):
			return not (self == other);

	def root(self):
		raise NotImplementedError();

	def parent(self, P):
		raise NotImplementedError();

	def size(self, p):
		" get number of children"
		raise NotImplementedError();

	def children(self, p):
		raise NotImplementedError();
	
	def __len__(self):
		"return total elements in the tree"
		raise NotImplementedError();

	def isRoot(self, p):
		return self.root() == p

	def isLeaf(self, p):
		return self.size(p) == 0

	def empty(self):
		return len(self) == 0;

	def depth(self, p):
		if self.isRoot(p):
			return 0;
		else:
			return 1+ self.depth(p.parent());
	def _height2(self, p):
		if self.isLeaf(p):
			return 0;
		else:
			return 1+max(self._height2(c) for c in self.children(p));

	def height(self, p = None ):
		if ( p == None ):
			p = self.root();
		return self._height2(p);


		
	def __init__(self):
		'''
		Constructor
		'''
		pass;
		

		
